class Solution {
public:
    int ans = 0;
    int movingCount(int threshold, int rows, int cols) {
        vector<vector<bool>> used(rows, vector<bool>(cols, false));
        return dfs(rows, cols, threshold, 0, 0, used);
    }
    int dfs(int rows, int cols, int thre, int i, int j, vector<vector<bool>>& used) {
        if(i < 0 || i >= rows || j < 0 || j >= cols || used[i][j] || !check(i, j, thre)) return 0;
        used[i][j] = true;
        return 1 + dfs(rows, cols, thre, i + 1, j, used) + dfs(rows, cols, thre, i - 1, j, used) + dfs(rows, cols, thre, i, j + 1, used) + dfs(rows, cols, thre, i, j - 1, used);
        
    }
    bool check(int i, int j, int thre) {
        int sum = 0;
        while(i) {
            sum += i % 10;
            i /= 10;
        }
        while(j) {
            sum += j % 10;
            j /= 10;
        }
        if(sum <= thre) return true;
        else return false;
    }
};